package Leetcode.动态规划;

public class 蛋糕最高价 {
    // 输入蛋糕价格列表 priceList ，求重量为 n 蛋糕的最高售价
   static int maxCakePrice1(int n, int[] priceList) {
        if (n <= 1) return priceList[n]; // 蛋糕重量 <= 1 时直接返回
        int f_n = 0;
        for(int i=0; i<n; i++){
            f_n = Math.max(f_n, maxCakePrice1(i, priceList) + priceList[n - i]);
        }
        return f_n;                      // 返回 f(n)
    }

    // 输入蛋糕价格列表 priceList ，求重量为 n 蛋糕的最高售价
    static int maxCakePrice2(int n, int[] priceList, int[] dp) {
        if (n <= 1) return priceList[n]; // 蛋糕重量 <= 1 时直接返回
        int f_n = 0;
        dp[1] = priceList[1];
        for(int i=0; i<n; i++){
            int f_i = dp[i] !=0 ? dp[i] :  maxCakePrice2(i, priceList, dp);
            f_n = Math.max(f_n, f_i + priceList[n-i]);
        }
        dp[n] = f_n;
        return dp[n];
    }

    static int maxCakePriceMemorized(int n, int[] priceList) {
        int[] dp = new int[n + 1];
        return maxCakePrice2(n, priceList, dp);
    }

    static int maxCakePrice3(int n, int[] priceList) {
        if (n <= 1) return priceList[n]; // 蛋糕重量 <= 1 时直接返回
        int f_n = 0;
        int[] dp = new int[n + 1];        // 初始化 dp 列表
        dp[1] = priceList[1];
        for (int j = 1; j <= n; j++) {
            for(int i = 0; i < j; i++){
                dp[j] = Math.max(priceList[j], dp[i] + priceList[j-i]);
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
        int [] priceList = {0,2,3,6,7,11,15};
        int n = 5;
        System.out.println(maxCakePrice1(n,priceList));
        System.out.println(maxCakePriceMemorized(n,priceList));
        System.out.println(maxCakePrice3(n,priceList));
    }
}
